They have never shared so much as a meal and could not fairly be called friends, their friends say. On some issues, like the death penalty, they are polar opposite icons of their parties. Through two bitter mayoral elections and two Republican Presidencies, they were pointed intellectual and oratorical adversaries.
But behind Mayor Rudolph W. Giuliani and Gov. Mario M. Cuomo's odd marriage of political expediency and prideful principle, those close to them say, lie months of mutual appreciation of the burdens of governing, and two lifetimes of common experience in class, outlook, education, law and public office.
Both are Italian-American descendants of immigrants, Mr. Giuliani from Brooklyn, Mr. Cuomo from Queens. The Mayor's father owned a tavern, the Governor's a grocery. Mr. Giuliani was schooled by the Christian Brothers at Bishop Loughlin High School, Mr. Cuomo by the Vincentian priests of St. John's University. And each won high office as a midlife maverick against the odds after serving in appointed posts.
Over seven years of common tenure with Mayor Edward I. Koch, and four with Mayor David N. Dinkins, the Governor never accepted unsolicited phone calls from those fellow Democrats without first having his top aides call theirs to find out what was afoot. He takes this Mayor's calls himself, mutual friends say.
"They speak the same language," said David Garth, the political strategist who advises them both and helped foster their bond.
Governors and mayors are natural adversaries -- in the competition for the spotlight, scarce public funds and the balancing of different constitutencies. In fact, several of Cuomo friends said the Mayor's endorsement on Monday, which Mr. Cuomo never actually asked for, except as a joke in a television interview, had caused the Governor to muse moodily about the burden such new-found friendship imposed since he might yet have to disagree with Mr. Giuliani when city-state interests collide.
But the combination of the first-year Mayor's popularity and three-term Governor's unpopularity -- together with their common contempt for their fellow Italian-American, Senator Alfonse M. D'Amato, who engineered the nomination of Mr. Cuomo's Republican opponent, State Senator George E. Pataki -- produced an unusual degree of alliance even before Mr. Giuliani's endorsement this week.
"Each of their experiences with the other has been a feeling that the other guy is always truthful in dealing," said Raymond B. Harding, the state Liberal Party leader, who is one of their principal matchmakers. "I know they both share that view. Now, whether they're at the stage of going out drinking and dancing, I don't believe it's come to that."
As long ago as Mr. Giuliani's first mayoral race in 1989, the Mayor once recalled, the Governor, never one to pass up a complex public argument, had given him a bit of friendly advice on how to sound less lawyerly in the context of a campaign, not a courtroom.
Last week, when Mr. Cuomo arrived late for a ground-breaking ceremony for The New York Times's production plant in Queens and asked the Mayor if he had missed anything, Mr. Giuliani felt comfortable enough to whisper back, "I endorsed you."
"I have to say I don't believe this is anything but a good old-fashioned political alliance," said Mitchell Moss, director of the Urban Research Center at New York University and a Cuomo supporter. "The bond just got very strong, though."
Mr. Moss noted that the Governor and Mayor had both won elective office relatively late in life and were not beholden to political machines, in contrast to Mr. D'Amato, who cut his teeth in the patronage-fueled Nassau County Republican organization and often seems to echo the roguish politicians of an earlier era. "I think they like to perceive themselves as above politics -- in politics, but not of politics," Mr. Moss said.
Associates said Mr. Giuliani had been particularly put off by Mr. Pataki's closeness to Mr. D'Amato and the fact that Mr. Pataki had never come to meet him alone, only with D'Amato loyalists. The Senator sponsored Mr. Giuliani as United States Attorney, but they fell to feuding after Mr. D'Amato made inquiries on behalf of defendants in some pending mob cases and Mr. Giuliani questioned as he left the job whether Mr. D'Amato would nominate a successor with enough integrity to pursue sensitive investigations.
By contrast, mayoral associates said, in the mid-1980's when Mr. Cuomo's hesitancy to run for President prompted speculation about whether he had ties to organized crime, Mr. Giuliani was steadfast in saying Mr. Cuomo had nothing to hide, and earned the Governor's gratitude.
"What I have noted about the two of them is that they're very independent thinkers and very much their own men and don't go by the conventional wisdom, and they do what they think is right," said the Governor's old friend, Meyer S. Frucher, who has never been known as a Giuliani fan.
Each man, their friends say, has something of an altar boy's sense of moral obligation in the face of a fallen world.
"I believe that is certainly true of the Mayor," said Mr. Harding. "Whether it comes in part from his Catholicism, I'm not astute enough to say. With respect to the Governor, I make fun of him to his face that he constantly communicates with Teilhard de Chardin," the French theologian Mr. Cuomo loves to quote.
